# Complexité Fibonacci

## Introduction

La suite de Fibonacci est un exemple intéressant pour comparer la complexité
en temps de calcul et occupation mémoire de plusieurs solutions algorithmiques.

La suite de Fibonacci est une suite de nombres (entiers) où chaque terme est
la somme des deux termes précédents, les deux premiers étant 0 et 1 : 0, 1, 1, 2, 3, 5, 8, ...

L'objectif est de comparer les complexités de différentes versions des fonctions
calculant la n-ième terme de la suite de Fibonacci :

- récursive — intuitive
- récursive avec **mémoïsation** (compromis temps-mémoire)
- itérative


## Bibliothèqe de fonctions

Ces fonctions ont été conçues a des fins pédagogiques. `fiborec` et `fibomemo`
sont récursives. Quelques précisions :

- `fiborec` a été adoptée à des fins pédagogiques, le code simplifié serait :

```python
def fiborec(n: int) -> int:
	return n if n <= 1 else fiborec(n - 1) + fiborec(n - 2)
		#ce qui correspond au code suivant:
		#if n <= 1:
			#v = n
		#else:
			#v = fiborec(n - 1) + fiborec(n - 2)
		#return v
```

- `fibomemo` nécessite un lanceur afin de concerver un profil
ergonomique (`fibomemo(k)`), alors qu'un second paramètre servant à mémoriser
le résultat des calculs est nécessaire.


```python
from typing import Dict, Callable

def fiborec(n: int) -> int:
	def _fiborec(n: int, lvl: int) -> int: #lvl: pour debug
		global cplx
		global debug
		cplx += 1
		if debug: print(" " * lvl * 2 + "Fibonacci(" + str(n) + ")")	#debug
		return n if n <= 1 else _fiborec(n-1, lvl+1) + _fiborec(n-2, lvl+1)
	return _fiborec(n, 0)

def fibomemo(n: int) -> int:
	def _fibomemo(n: int, lvl: int, mem: Dict) -> int: #lvl: pour debug
		global cplx
		global debug
		if n in mem.keys():
			r = mem[n]
		else:
			cplx += 1
			if debug: print(" " * lvl * 2 + "Fibonacci(" + str(n) + ")")	#debug
			r = n if n <= 1 else _fibomemo(n-1, lvl+1, mem) +  _fibomemo(n-2, lvl+1, mem)
			mem[n] = r
		return r
	return _fibomemo(n, 0, {})

def fiboite(n: int) -> int:
	global cplx
	global debug
	a, b = 0, 1
	if debug: print("Fibonacci(0)")	#debug
	cplx += 1 #Fibonacci(0)
	for i in range(n):
		if debug: print("Fibonacci(" + str(i+1) + ")")	#debug
		cplx += 1
		c = a + b
		a = b
		b = c
	return a

def suitefibo(n: int):
	global debug
	_debug = debug	#enregistre l'état
	debug = False
	for i in range(1, n + 1):
		run(i, fiboite)
	debug = _debug	#restore l'état

debug = True
def run(n: int, fun: Callable[[int], int]):
	global cplx
	cplx = 0
	fibo = fun(n)
	print("Fibo(" + str(n) + ") = " + str(fibo))
	if debug: print("Complexité : " + str(cplx))
```

## Expérimentation

Afficher la suite de fibonacci avec l'instruction `suitefibo(10)`. Observer
que chaque terme est la somme des deux termes précédents (fibo(4) = fibo(3) + fibo(2)).

La fonction `run` sert d'enveloppe pour afficher le résultat et la complexité
en temps (de calcul) ; elle s'utilise de la façon suivante : `run(5, fiborec)`
ou `run(10, fiboite)`…

Analyser la pile des appels de fonction pour la fonction `fiborec`.